#include<vector>
using namespace std;
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        //利用前缀积 和 后缀积 的思想 
        //前缀积 f[i]表示从0到i-1的乘积，其中f[0] = 1；
        //后缀积 g[i]表示从 i+1到 n-1的乘积 其中g[n-1] = 1;
        int n = nums.size();
        vector<int> f(n) , g(n) ,ret(n);
        f[0] = g [n-1] = 1;
        for(int i = 1 ; i < n ; i++){
            f[i] = f[i-1]*nums[i-1];
        }
        for(int i= n-2 ; i >= 0 ; i--){
            g[i] = g[i+1]*nums[i+1];
        }
        for(int i = 0 ; i < n ; i++){
            ret[i] = g[i] * f[i];
        }
        return ret;
    }
};